package cn.hdr.train.lc;

import cn.hdr.train.bean.ListNode;
import cn.hdr.train.bean.TreeNode;
import javafx.util.Pair;

import java.util.*;

public class LCTestA {


    /**
     * 删除链表中等于给定值 val 的所有节点。
     *
     * 示例:
     *
     * 输入: 1->2->6->3->4->5->6, val = 6
     * 输出: 1->2->3->4->5
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode start = new ListNode(val);
        start.next = head;
        ListNode pre = start;
        ListNode cur = head;
        while (cur != null){
            if(cur.val == val){
                pre.next = pre.next.next;
            }else {
                pre = pre.next;
            }
            cur = cur.next;
        }
        return start.next;
    }

    /**
     * 统计所有小于非负整数 n 的质数的数量。
     *
     * 示例:
     *
     * 输入: 10
     * 输出: 4
     * 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
     */
    public static int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        // 首先去掉一半的偶数
        int count = n / 2;
        boolean[] isPrimes = new boolean[n];
        for (int i = 3; i * i < n; i += 2) {
            // 不是质数 => continue
            if (isPrimes[i]) {
                continue;
            }
            for (int j = i * i; j < n; j += 2 * i) {
                if (!isPrimes[j]) {
                    count--;
                    isPrimes[j] = true;
                }
            }
        }
        return count;
    }

    public static int countPrimes2(int n) {
        boolean[] isPrim = new boolean[n];
        int count = n - 2;
        for (int i = 2; i * i < n; i++)
            if (!isPrim[i])
                for (int j = i * i; j < n; j += i){
                    if (!isPrim[j]) {
                        count--;
                        isPrim[j] = true;
                    }
                }

        return count;
    }

    /**
     * 给定两个字符串 s 和 t，判断它们是否是同构的。
     *
     * 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
     *
     * 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
     *
     * 示例 1:
     * 输入: s = "egg", t = "add"
     * 输出: true
     *
     * 示例 2:
     * 输入: s = "foo", t = "bar"
     * 输出: false
     *
     * 示例 3:
     * 输入: s = "paper", t = "title"
     * 输出: true
     *
     */
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length())
            return false;

        char[] lmap = new char[128];
        char[] rmap = new char[128];
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        for (int i = 0; i < sarr.length; i++) {
            char replace = lmap[sarr[i]];
            if(replace == 0){
                replace = rmap[tarr[i]];
                if(replace == 0){
                    replace = tarr[i];
                    lmap[sarr[i]] = replace;
                    rmap[replace] = sarr[i];
                }else if(replace != sarr[i]){
                    return false;
                }
            }
            sarr[i] = replace;

            if(sarr[i] != tarr[i])
                return false;
        }
        return true;
    }

    /**
     * 翻转一棵二叉树。
     *
     * 示例：
     *
     * 输入：
     *      4
     *    /   \
     *   2     7
     *  / \   / \
     * 1   3 6   9
     *
     * 输出：
     *      4
     *    /   \
     *   7     2
     *  / \   / \
     * 9   6 3   1
     *
     */
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return null;
        if(root.left == null && root.right == null)
            return root;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }


    /**
     * 给定二叉树 [3,9,20,null,null,15,7],
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回它的最小深度  2.
     *
     */
    public int minDepth(TreeNode root) {
        LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
        if (root == null) {
            return 0;
        }
        else {
            stack.add(new Pair<>(root, 1));
        }

        int current_depth = 0;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> current = stack.poll();
            root = current.getKey();
            current_depth = current.getValue();
            if ((root.left == null) && (root.right == null)) {
                break;
            }
            if (root.left != null) {
                stack.add(new Pair<>(root.left, current_depth + 1));
            }
            if (root.right != null) {
                stack.add(new Pair<>(root.right, current_depth + 1));
            }
        }
        return current_depth;
    }


    /**
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     *
     *  
     *
     * 示例：
     *
     * 输入：n = 3
     * 输出：[
     *        "((()))",
     *        "(()())",
     *        "(())()",
     *        "()(())",
     *        "()()()"
     *      ]
     *
     */
    public List<String> generateParenthesis(int n) {
        if(n == 0)
            return null;
        if(n == 1){
            return Collections.singletonList("()");
        }

        List<String> list = generateParenthesis(n - 1);
        Set<String> set = new HashSet<>();
        for (String str:list) {
            StringBuilder sb = new StringBuilder();
            sb.append('(');
            sb.append(str);
            sb.append(')');
            set.add(sb.toString());
            sb = new StringBuilder();
            sb.append('(');
            sb.append(')');
            sb.append(str);
            set.add(sb.toString());
            sb = new StringBuilder();
            sb.append(str);
            sb.append('(');
            sb.append(')');
            set.add(sb.toString());
        }

        return new ArrayList<>(set);
    }


    private boolean isTruePar(String str){
        char[] stack = new char[str.length()];

        int point = -1;
        for (int i = 0; i < str.length(); i++) {
            if(point == -1){
                if(str.charAt(i) == ')'){
                    return false;
                }else {
                    stack[++point] = str.charAt(i);
                }
                continue;
            }
            char peek = stack[point];
            if(peek == '(' && str.charAt(i) == ')'){
                point--;
            }else if(str.charAt(i) == ')'){
                return false;
            } else {
                stack[++point] = str.charAt(i);
            }
        }

        return point == -1;
    }

    /**
     * 给定有序数组: [-10,-3,0,5,9],
     *
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return support(nums,0,nums.length-1);
    }

    private TreeNode support(int[] nums, int start, int end){
        if(start > end) return null;
        int mid = (start + end) >> 1;
        TreeNode root = new TreeNode(mid);
        TreeNode left = support(nums,start,mid - 1);
        TreeNode right = support(nums,mid + 1,end);
        root.left = left;
        root.right  = right;
        return root;
    }


    /**
     * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 示例 1:
     *
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * 示例 2:
     *
     * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     *
     */
    @SuppressWarnings("all")
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int t:nums) {
            queue.add(t);
            if(queue.size() > k){
                queue.poll();
            }
        }
        return queue.peek();
    }
}